package com.mojito.learn.algorithm.leetcode;

import com.mojito.learn.algorithm.datastructure.ListNode;
import com.mojito.learn.algorithm.datastructure.TreeNode;

import java.util.*;

/**
 * @author liufq
 * @date 2021-07-02 17:43:39
 */
public class LeetCode0 {

    /**
     * 1. 两数之和
     */
    public int[] twoSum(int[] nums, int target) {
        // 暴力枚举
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }

        // 哈希表
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    /**
     * 2. 两数相加
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode();
        ListNode resTemp = res;
        int nextSum = 0;
        int flag = 0; // 标识相加进1
        while (l1 != null && l2 != null) {
            int p;
            if (flag == 0) {
                p = l1.val + l2.val;
                res.val = p % 10;
                nextSum = p / 10;
                flag++;
            } else {
                p = l1.val + l2.val + nextSum;
                resTemp.next = new ListNode(p % 10);
                resTemp = resTemp.next;
                nextSum = p / 10;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 != null) {
            int p = l1.val + nextSum;
            resTemp.next = new ListNode(p % 10);
            resTemp = resTemp.next;
            nextSum = p / 10;
            l1 = l1.next;
        }
        while (l2 != null) {
            int p = (l2.val + nextSum);
            resTemp.next = new ListNode(p % 10);
            resTemp = resTemp.next;
            nextSum = p / 10;
            l2 = l2.next;
        }
        if (nextSum != 0) resTemp.next = new ListNode(nextSum);
        return res;
    }

    /**
     * 3. 无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String s, int... type) {
        return type[0] == 0 ? lengthOfLongestSubstring0(s) : lengthOfLongestSubstring1(s);
    }

    /**
     * 自己的解法：击败5%，从动态规划入手存储每个字符到其他字符是否有重复字符，再改造临时变量存，再优化成现在这样
     */
    private int lengthOfLongestSubstring0(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }

        int result = 1;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (s.substring(i, j).contains(String.valueOf(s.charAt(j)))) {
                    break;
                } else {
                    if (j - i + 1 > result) {
                        result = j - i + 1;
                    }
                }
            }
        }
        return result;
    }

    /**
     * 官方解法：使用滑动窗口（左右指针作为边界移动），使用hash判断重复字段
     */
    private int lengthOfLongestSubstring1(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    /**
     * 5. 最长回文子串
     */
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        // 存储字符串从任意位置到另一个位置是否是回文
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = true;
        }
        int start = 0;
        int length = 1;
        for (int j = 1; j < s.length(); j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) {
                    if (j - i >= length) {
                        start = i;
                        length = j - i + 1;
                    }
                }
            }
        }
        return s.substring(start, start + length);
    }

    /**
     * 7. 整数反转
     */
    public int reverse(int x) {
//        if (x < 10 && x > -10) {
//            return x;
//        }
//
//        int ans = 0;
//        do {
//            ans = ans * 10 + x % 10;
//            x /= 10;
//        } while (x / 10 != 0);
//
//        ans = ans * 10 + x % 10;
//        return (ans < Integer.MIN_VALUE / 10 || ans > Integer.MAX_VALUE / 10) ? 0 : ans;

        int rev = 0;
        while (x != 0) {
            if (rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }

    /**
     * 9. 回文数
     */
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int temp = 0;
        while (x > temp) {
            temp = temp * 10 + x % 10;
            x /= 10;
        }
        return x == temp || x == temp / 10;
    }

    /**
     * 10. 正则表达式匹配
     */
    public boolean isMatch(String s, String p) {
        boolean[] dp = new boolean[s.length()];
        dp[s.length() - 1] = p.contains(String.valueOf(s.charAt(s.length() - 1)));
        for (int i = 0; i < s.length() - 1; i++) {
//            dp[i] =
        }
        return true;
    }

    /**
     * 20. 有效的括号
     */
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }

        Map<Character, Character> map = new HashMap<Character, Character>() {{
            put(')', '(');
            put('}', '{');
            put(']', '[');
        }};

        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char item : chars) {
            if (stack.isEmpty()) {
                stack.push(item);
                continue;
            }

            Character peek = stack.peek();
            Character c = map.get(item);
            if (c != null) {
                if (c.equals(peek)) {
                    stack.pop();
                    continue;
                } else {
                    return false;
                }
            }
            stack.push(item);
        }
        return stack.isEmpty();
    }

    /**
     * 21. 合并两个有序链表
     *
     * 解题思路：递归遍历，判断临界条件
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }

        ListNode listNode = new ListNode();
        if (list1.val > list2.val) {
            listNode.val = list2.val;
            list2 = list2.next;
        } else {
            listNode.val = list1.val;
            list1 = list1.next;
        }
        listNode.next = mergeTwoLists(list1, list2);
        return listNode;
    }

    /**
     * 28. 实现 strStr()
     */
    public int strStr(String haystack, String needle, int... type) {
        return type[0] == 0 ? strStr0(haystack, needle) : strStr1(haystack, needle);
    }

    /**
     * 暴力迭代实现
     */
    private int strStr0(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = false;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                return i;
            }
        }
        return -1;
    }

    /**
     * KMP
     */
    private int strStr1(String haystack, String needle) {
        return 0;
    }

    /**
     * 53. 最大子序和
     */
    public int maxSubArray(int[] nums) {
        int result = nums[0];
        int prev = 0;
        for (int i = 0; i < nums.length; i++) {
            prev = Math.max(prev + nums[i], nums[i]);
            result = Math.max(result, prev);
        }
        return result;
    }

    /**
     * 62. 不同路径
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[1][0] = 0;
        dp[0][1] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 && j == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 94. 二叉树的中序遍历
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traversal(root, result);
        return result;
    }

    private void traversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        traversal(root.left, result);
        result.add(root.val);
        traversal(root.right, result);
    }
}
